package com.fanshuai.algorithms.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 八皇后问题
 */
public class EightQueen {
    public List<List<Integer>> eightQueen() {
        List<List<Integer>> solutions = new ArrayList<>();
        eightQueen(1, new ArrayList<>(), solutions);
        return solutions;
    }

    private void eightQueen(int i, List<Integer> path, List<List<Integer>> solutions) {
        if (i > 8) {
            solutions.add(new ArrayList<>(path));
        }

        for (int j = 1; j <= 8; j++) {
            if (queenValid(path, j)) {
                path.add(j);
                eightQueen(i + 1, path, solutions);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean queenValid(List<Integer> list, int pos) {
        int last = list.size();
        for (int i = last - 1; i >= 0; i--) {
            int queen = list.get(i);
            //同一列不能相遇
            if (queen == pos) {
                return false;
            }
            //同一斜行不能相遇
            if (pos - queen == last - i) {
                return false;
            }
            //同一斜行不能相遇
            if (queen - pos == last - i) {
                return false;
            }
        }
        return true;
    }
}
